/**
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 *
 *题解：https://leetcode.cn/problems/permutations-ii/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liwe-2/
 */
class PermuteUnique {
    List<List<Integer>> ret=new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int len=nums.length;
        boolean[] used=new boolean[len];
        Deque<Integer> qu=new LinkedList<>();
        permuteUnique(nums,qu,used,len,0);
        return ret;
    }
    public void permuteUnique(int[] nums,Deque<Integer> qu,boolean[] used,int len,int depth){
        if(depth==len){
            ret.add(new ArrayList<>(qu));
        }
        for(int i=0;i<len;i++){
            if(i>0&&nums[i-1]==nums[i]&&!used[i-1]){//如果有重复的就跳过本次循环
               continue;
            }
            if(!used[i]){
                used[i]=true;
                qu.addLast(nums[i]);
                permuteUnique(nums,qu,used,len,depth+1);
                used[i]=false;
                qu.removeLast();
            }
        }
    }
}